from typing import List


class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        # matrix = [[0] * n for _ in range(n)]
        # row, col, dirIdx = 0, 0, 0
        # for i in range(n * n):
        #     matrix[row][col] = i + 1
        #     dx, dy = dirs[dirIdx]
        #     r, c = row + dx, col + dy
        #     if r < 0 or r >= n or c < 0 or c >= n or matrix[r][c] > 0:
        #         dirIdx = (dirIdx + 1) % 4  # 顺时针旋转至下一个方向
        #         dx, dy = dirs[dirIdx]
        #     row, col = row + dx, col + dy
        #
        # return matrix

        locations = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        matrix = [[0] * n for _ in range(n)]
        row, col, locationIndex = 0, 0, 0
        for i in range(n * n):
            matrix[row][col] = i + 1
            x, y = locations[locationIndex]
            r, c = row + x, col + y
            if r >= n or r < 0 or c >= n or c < 0 or matrix[r][c] > 0:
                locationIndex = (locationIndex + 1) % 4
                x, y = locations[locationIndex]
            row, col = row + x, col + y

        return matrix


if __name__ == '__main__':
    s = Solution()
    print(s.generateMatrix(3))
    print(s.generateMatrix(4))
